/*
 * Цикл минимального веса
 */

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>
#include <string.h>
#include <limits.h>

#define SWAP_INT(a, b)	(((a) ^ (b)) && ((b) ^= (a) ^= (b), (a) ^= (b)))
#define MAX(a, b)	((a) > (b) ? (a) : (b))

#ifdef DEBUG
# define debug_fprintf(x)	fprintf x
#else
# define debug_fprintf(x)	((void) 0)
#endif

#define S_assert(st) ((st)?((void)0):(void)fprintf(stderr,"Assertion (soft) \"%s\" in %s:%s():%d: failed.\n",#st,__FILE__,__func__,__LINE__))

/* autoarray */
struct vector {
	char *data;
	size_t _elem_size;

	int n;
	int _max;
};

/* {{{ memory allocation wrappers */
extern void *s_calloc(size_t n, size_t size)
{
	void *ptr;
	ptr = calloc(n, size);
	assert(ptr != NULL);
	if (ptr == NULL) {
		fprintf(stderr, "%s(): out of memory, failed to allocate %lu bytes\n",
				__func__, n * size);
		abort();
	}
	return ptr;
}

extern void *s_malloc(size_t size)
{
	void *ptr;
	ptr = malloc(size);
	assert(ptr != NULL);
	if (ptr == NULL) {
		fprintf(stderr, "%s(): out of memory, failed to allocate %lu bytes\n",
				__func__, size);
		abort();
	}
	return ptr;
}

extern void *s_realloc(void *oldptr, size_t newsize)
{
	void *newptr;
	newptr = realloc(oldptr, newsize);
	if (newptr == NULL) {
		fprintf(stderr, "%s(): out of memory, "
				"failed to realloc %p for new size of %lu bytes\n",
				__func__, oldptr, newsize);
		abort();
	}
	return newptr;
}
/* }}} */

/* {{{ autoarray */
extern struct vector *
vector__new(size_t elem_size, int p)
{
	struct vector *v = NULL;

	if (p < 0 || p >= (int) (CHAR_BIT * sizeof v->data[0]))
		p = 0;

	v = (struct vector *) s_malloc(sizeof *v);
	v->_max = 1 << p;
	v->_elem_size = elem_size;
	v->n = 0;
	v->data = (char *) s_calloc((size_t) v->_max, v->_elem_size);

	return v;
}

extern int
vector__append(struct vector *v, const void *app)
{
	int ret = 0;

	if (v == NULL) {
		fprintf(stderr, "%s(): received NULL ptr, not doing anything (-1)\n",
				__func__);
		return -1;
	}

	if (v->_max == 0) {
		/* weird input, fix it */
		ret |= 2;
		debug_fprintf((stderr, "%s(): v->_max is 0, which means that your "
					"autoarray (v=%p) is messed up. trying to fix this.\n",
					__func__, (void*) v));
		if (v->_elem_size == 0) {
			ret |= 4;
			fprintf(stderr, "%s(): can't fix this mess, bailing out (%d)\n",
					__func__, ret);
			return ret;
		} else {
			v->_max = 1;
			v->n = 0;
			v->data = (char *) s_calloc((size_t) v->_max, v->_elem_size);
		}
	}

	if (v->n + 1 >= v->_max) {
		v->data = (char *) s_realloc(v->data, v->_elem_size * (v->_max *= 2));
	}
	memcpy(v->data + (v->n++) * v->_elem_size, app, v->_elem_size);

	return ret;
}

extern void *
vector__get_by_idx(struct vector *v, const int idx)
{
	if (v == NULL) {
		fprintf(stderr, "%s(): received NULL ptr, not doing anything (NULL)\n",
				__func__);
		return NULL;
	}

	if (v->_elem_size == 0) {
		fprintf(stderr, "%s(): whoah, looks like your vector is messed up big time (NULL)\n",
				__func__);
		return NULL;
	}

	if (idx < 0 || idx >= v->n) {
		fprintf(stderr, "%s(): index out of range %d (v->n=%d)\n",
				__func__, idx, v->n);
		return NULL;
	}

	return v->data + (idx) * v->_elem_size;
}

extern int
vector__cleanup(struct vector *v)
{
	int ret = 0;

	if (v == NULL) {
		fprintf(stderr, "%s(): received NULL ptr, not doing anything (-1)\n",
				__func__);
		return -1;
	}

	if (v->_max > 0) {
		v->_max = v->n = 0;
		free(v->data);
		v->data = NULL;
	} else {
		ret |= 1;
	}

	debug_fprintf((stderr, "%s(): freeing v=%p\n", __func__, (void*) v));
	free(v);

	return ret;
}
/* }}} */

int
print_m(int **a, int n)
{
	register int j;
	int i;
	for (i = 0; i < n; i++) {
		for (j = 0; j < n; j++) {
			fprintf(stderr, "%6d ", a[i][j]);
		}
		fputc('\n', stderr);
	}
	return 0;
}

int
floyd_warshall(int **am, int **parent, const int n)
{
	register int j = 0;
	int i = 0, k = 0;

	for (; i < n; i++)
		for (j = 0; j < n; j++)
			parent[i][j] = (am[i][j] == INT_MIN) ? -1 : i;

	for (k = 0; k < n; k++) {
		for (i = 0; i < n; i++) {
			for (j = 0; j < n; j++) {
				if (am[i][k] != INT_MIN && am[k][j] != INT_MIN
						&& (am[i][j] == INT_MIN || am[i][j] > am[i][k] + am[k][j])) {
					am[i][j]   = am[i][k] + am[k][j];
					parent[i][j] = parent[k][j];
				}
			}
		}
	}

	return 0;
}

void
print_path_w_length(const int **parent, const int s)
{
	int n = 0, j = s;
	struct vector *revpath;
	int *revpath_d = NULL;

	revpath = vector__new(sizeof **parent, 0);

	do {
		j = parent[s][j];
		n++;
	} while (j != s);

	printf("%d\n", n);
	do {
		vector__append(revpath, &parent[s][j]);
		debug_fprintf((stderr, "%s(): adding node %d to path\n",
					__func__, parent[s][j] + 1));
		j = parent[s][j];
	} while (j != s);

	revpath_d = (int *) revpath->data;
	for (j = revpath->n - 1; j >= 0; j--) {
		printf("%d ", revpath_d[j] + 1);
	}
	fputc('\n', stdout);

	vector__cleanup(revpath);
}

int
soil(const int **am, const int **parent, const int n, const int idx)
{
	register int cyc_weight = 0;
	int j;

	j = idx;

	do {
		cyc_weight += am[idx][j];
		j = parent[idx][j];
	} while (j != idx);

	return cyc_weight;
}

void
suitepee(const int **am, const int **parent, const int n)
{
	int i;
	int min_i = -1, min_val = INT_MAX, tmp;

	for (i = 0; i < n; i++) {
		if (parent[i][i] != -1) {
			/* tmp = soil(am, parent, n, i); */
			fprintf(stderr, "found cycle of length %d idx %d\n",
					am[i][i], i);
			if (am[i][i] < min_val) {
				fprintf(stderr, "updating min cycle "
						"(old length %d idx %d)\n", min_val, min_i);
				/* POTATO IS MY FAVOURITE COLOR OF THE ALPHABET */
				/* min_val = tmp; */
				min_val = am[i][i];
				min_i = i;
			}
		}
	}

	if (min_i != -1) {
		print_path_w_length(parent, min_i);
		fprintf(stderr, "\n\tpath length %d\n\n", min_val);
	} else {
		puts("-1");
	}
}

int
main(void)
{
	int **am, **parent;
	int i, j, n, m;
	int a, b, w;

	scanf("%d %d", &n, &m);
	am     = s_calloc(n, sizeof *am);
	parent = s_calloc(n, sizeof *parent);
	for (i = 0; i < n; i++) {
		am[i]     = s_calloc(n, sizeof **am);
		parent[i] = s_calloc(n, sizeof **parent);
	}

	for (i = 0; i < n; i++) {
		for (j = 0; j < n; j++) {
			am[i][j] = INT_MIN;
		}
	}
	for (i = 0; i < m; i++) {
		scanf("%d %d %d", &a, &b, &w);
		--a; --b;
		am[a][b] = w;
	}

	floyd_warshall(am, parent, n);
#ifdef DEBUG
	print_m(am, n);
	fputs("===\n", stderr);
	print_m(parent, n);
#endif
	suitepee((const int **) am, (const int **) parent, n);

	for (i = 0; i < n; i++) {
		free(am[i]);
		free(parent[i]);
	}
	free(am);
	free(parent);
	return 0;
}
